function A = nRestrictedGraph(n, size, dropTime, stay)
%% The function nRestrictedGraph creates a graph with the following
%% conditions:
%% -A is the adjacency matrix for the n-restricted graph, if A(i,j) = 1 then
%% there is an arc from node i to node j, if A(i,j) = 0; no arc from i to j
%% -size is the number of nodes in the graph, which could be infinite
%% -dropTime is the number of turns it takes for the bomb to explode after it
%% has been dropped
%% -stay is a boolean which is true if the boat does not need to move every
%% turn

%% the nodes are numbered in a breadth-first way

if(size==inf)
    %first determine the size (number of nodes) of the useful part of the 
    %infinite graph: s
    s = 1;
    for i=1:dropTime
    	s = s + n^(i-1)*(n+1);
    end
    
    %A is the adjacency matrix filled with zeroes, so now we will determine
    %where the arcs are
    A = zeros(s);
    
    for i=1:s
        %if the ship is allowed to stay at its place, add the arc from the
        %node to itself
        if(stay)
        	A(i,i) = 1;
        end

        %we will determine where the arcs next of the next node are based 
        %on where the arcs of the previous node are
        %so we first determine where these last arcs are
        if(i>1)
        	lastArcs = zeros(n+1,1);
           m = 1;
            for l=1:length(A)
                if(A(i-1,l) == 1)
                	lastArcs(m) = l;
                	m=m+1;
                end
            end
        end
                
        if(i==1)
            %at the first node, the arcs are going the the n+1 following
            %nodes
            for j=1:n+1
            	A(i,i+j) = 1;
            end
        elseif(i<=n+2)
            %for the n+1 "second layer" nodes, create an arc back to node
            %1, then determine every other arc
            A(i,1) = 1;
            if(lastArcs(length(lastArcs))>0 && lastArcs(length(lastArcs))<length(A))
                for j=1:n
                    A(i,lastArcs(length(lastArcs))+j) = 1;
                end
            end
        else
            %for the rest of the nodes, first determine to which node the
            %"backwards" arc has to go, then determine where the remaining 
            %n "forward" arcs are going
            
            c = (i-3)/n;
            if(mod(c,1)==0)
            	A(i,lastArcs(1)+1) = 1;
            else
            	A(i,lastArcs(1)) = 1;
            end
            
            if(lastArcs(length(lastArcs))>0 && lastArcs(length(lastArcs))<length(A))
            	for j=1:n
                	A(i,lastArcs(length(lastArcs))+j) = 1;
            	end
            end
            
        end
    end
else
    % size = [#rows, #columns]
    
    if(n==2)
        % #columns must be even!
        A = zeros(size(1)*size(2));
        
        for i=1:(size(1)*size(2))
            if(stay)
                A(i,i) = 1;
            end
            if(i>1)
                A(i,i-1) = 1;
            end
            if(i<size(1)*size(2))
                A(i,i+1) = 1;
            end
            if(mod(i,size(2)) > 1)
                if(mod(i,2)==0 && i<(size(1)-1)*size(2))
                    A(i,((i-mod(i,size(2)))/size(2)+2)*size(2)-(mod(i,size(2))-1)) = 1;
                elseif(mod(i,2)==1 && i>size(2))
                    A(i,((i-mod(i,size(2)))/size(2))*size(2)-(mod(i,size(2))-1)) = 1;
                end
            end
        end
    end
end